#define DEBUG
#include <cstdio>
#define INF 0x7ffffff
#define MAXNM 200
#define MAXLOGNM 8
#define MAXP 50000

using namespace std;

int min(int a, int b) {
  return a<b ? a : b;
}

int max(int a, int b) {
  return a>b ? a : b;
}

int main() {
#ifdef DEBUG
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
#endif

  int test;
  scanf("%d", &test);
  for (int testi=1; testi<=test; testi++) {
    static int t[MAXLOGNM*MAXNM+1], u[MAXLOGNM*MAXNM+1], x[MAXLOGNM*MAXNM+1], y[MAXLOGNM*MAXNM+1];
    int n, m, p, lenfood=0, lentool=0;
    scanf("%d %d %d", &n, &m, &p);
    for (int i=1; i<=n; i++) {
      int tt, tu, tv;
      scanf("%d %d %d", &tt, &tu, &tv);
      for (int j=1; j<=tv; j<<=1) {
	t[++lenfood] = tt*j;
	u[lenfood] = tu*j;
	tv -= j;
	if ((j<<1)>tv && tv>0) {
	  t[++lenfood] = tt*tv;
	  u[lenfood] = tu*tv;
	}
      
      }
    }
    for (int i=1; i<=m; i++) {
      int tx, ty, tz;
      scanf("%d %d %d", &tx, &ty, &tz);
      for (int j=1; j<=tz; j<<=1) {
	x[++lentool] = tx*j;
	y[lentool] = ty*j;
	tz -= j;
	if ((j<<1)>tz && tz>0) {
	  x[++lentool] = tx*tz;
	  y[lentool] = ty*tz;
	}
      }
    }

    static int f[MAXP+1];
    for (int i=1; i<=MAXP; i++) {
      f[i] = INF;
    }
    for (int i=1; i<=lenfood; i++) {
      for (int j=p; j>=0; j--) {
	if (j>=t[i]) {
	  f[j] = min(f[j-t[i]]+u[i], f[j]);
	} else {
	  f[j] = min(f[0]+u[i], f[j]);
	}
      }
    }

    static int g[MAXP+1];
    int ans=INF;
    for (int i=0; i<=MAXP; i++) {
      g[i] = 0;
    }
    for (int i=1; i<=lentool; i++) {
      for (int j=min(ans, MAXP); j>=0; j--) {
	if (j>=y[i]) {
	  g[j] = max(g[j], g[j-y[i]]+x[i]);
	}
	if (g[j]>=f[p]) {
	  ans = j;
	}
      }
    }
    #ifdef DEBUG
    printf("Lenfood:%d; Lentool:%d\n", lenfood, lentool);
    #endif

    if (ans<=MAXP) {
      printf("%d\n", ans);
    } else {
      printf("TAT\n");
    }
  }

  fcloseall();
  return 0;
}
